package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/construct-string-from-binary-tree/description
 * 题型：二叉树的前序遍历
 *
 * ```
 * 606. 根据二叉树创建字符串
 * 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
 * 空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
 *
 * 示例 1：
 * 输入：root = [1,2,3,4]
 * 输出："1(2(4))(3)"
 * 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
 *
 * 示例 2：
 * 输入：root = [1,2,3,null,4]
 * 输出："1(2()(4))(3)"
 * 解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
 * ```
 */
class leetcode_606 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root: TreeNode = n1
        n1.left = n2
        n1.right = n3
        n2.left = n4
        val actual = tree2str(root)
        val expected = "1(2(4))(3)"
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root: TreeNode = n1
        n1.left = n2
        n1.right = n3
        n2.right = n4
        val actual = tree2str(root)
        val expected = "1(2()(4))(3)"
        Assert.assertEquals(expected, actual)
    }

    fun tree2str(root: TreeNode?): String {
        /**
        题型：二叉树的前序遍历
        思路：观察规律：
        +当前节点
        若左孩子不空，+(左子树)
        右孩子不空，IF左孩子为空+(), +(右子树)
         */
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if(null == root){
            return ""
        }
        // 3 确定单层递归的处理逻辑: 前序遍历
        // 中
        var string: String = root.`val`.toString()

        // 左
        // 若左孩子不空，拼接左孩子: (左孩子)
        root.left?.let{
            string = string + "(" + tree2str(it)+ ")"
        }

        // 右
        // 若右孩子不空，若左孩子为空时，拼接：()，然后拼接右孩子：（右孩子）
        root.right?.let{
            // 左孩子为空时，拼接()
            if(root.left == null ){
                string = string + "(" +  ")"
            }
            string = string + "(" + tree2str(it) +")"
        }
        return string
    }
}